Ch 8 Roots of Equation

UTG

CPE 332

Computer Engineering

Mathematics II

Week 11

Part III, Chapter 9

Roots of Equations

Today Topics

• Roots of Equation

• Bracketing Method

– Bisection Method

– False Position Method

• Open Method

– Simple One-Point Iteration

– Newton-Ralphson Method

– Secant Method

– Multiple Roots Problem

– Modified Method

Roots of Equations

Zeroes of Functions

• กําหนด Function y=f(x)

– Zeroes ของ Function คือค่าของ x ที่ทําให ้

f(x)=0 หรือค่า y=0

– คือราก(root) ของสมการ f(x)=0 นั่นเอง

• ตัวอย่าง y=x3-2x2+x-5

– สมการ Polynomial, degree = 3

– ถ ้าเกิน Quadratic (Degree = 2) การหาราก

จะทําได ้ยาก, ไม่มีวิธีทาง Analytic Method โดยตรง เหมือน y=Ax2+Bx+C=0

2

b ± b − 4 ac x =

2 a

Zeroes of Functions

• ตัวอย่าง y=x3-2x2+x-5

– วิธีทาง Numerical ที่เราเคยเรียนมาในวิชา

เรขาคณิตย์ คือ Plot Graph และหารากของ

สมการจาก Graph

• 1. แต่วิธีนี้จะให ้ค่าที่หยาบ

• 2. กรณีที่เป็น Complex Root จะหาไม่ได ้ จาก

Graph

Zeroes of Functions

y=x3-2x2+x-5

2.4

Zeroes of Functions

y=x3-2x2+x-5

4334

.

2

x = − 2167

.

+ j 417

.

1

− 2167

.

j 417

.

1

2.4

Roots of Equation

• วิธีที่จะกล่าวต่อไป

– Numerical Method = Algorithm

– หา Zero Crossing (รากที่เป็นค่าจริง)

– สามารถได ้คําตอบให ้ถูกต ้องด ้วย Significant Digit มากเท่าที่เราต ้องการ

• ต ้อง Run Algorithm นานขึ้น

• Algorithm จะต ้อง Converge

– เป็น Iterative Method

• ถ ้า Algorithm Converge, แต่ละ Iteration ที่

Run จะให ้คําตอบที่ถูกต ้องขึ้นเรื่อยๆ

• จะช ้าหรือเร็วขึ้นอยู่กับ Convergence Rate ของแต่

ละ Algorithm

Methods

• Bracketing Method

– Bisection

– False Position

• Open Method

– Simple one-point Iteration

– Newton-Ralphson

– Secant Method

Bracketing Method

• ใช ้หลักความจริงที่ว่า เมื่อ f(x)=0 มันจะต ้อง

เปลี่ยนเครื่องหมาย

– ดังนั้น f(x-)f(x+) < 0 เมื่อ f(x)=0

• เราเริ่มจาก สองค่าของ x คือ xl และ xu ที่มี

คุณสมบัติ f(xl)f(xu) < 0

– อย่างน ้อยต ้องมีคําตอบหนึ่งอยู่ในช่วงนี้

• Algorithm จะ Search หาคําตอบในช่วง

Bracket นี้ โดยจะลดขนาดของ Bracket ลง

เรื่อยๆ

Bracketing Method

f ( x ) f ( x ) < 0

l

u

( x , f ( x )) u

u

xl

xu

( x , f ( x )) l

l

Bracketing Method

f ( x ) f ( x ) = 81

− < 0

l

u

(

)

9

,

7

x = 4

l

x = 7

u

( ,

4 − )

9

Bracketing Method:Bisection

Bracketing Method

x = (4 + 7) / 2 = 5.5

r

(

)

9

,

7

x = 4

l

x = 7

u

( ,

4 9

− )

Bracketing Method

x = (4 + 7) / 2 = 5.5

r

(

)

9

,

7

x = 4

x = 7

l

u

( x , f ( x )) r

r

.

5

(

,

5 − .

2

)

25

( ,

4 9

− )

xu=xr

Bracketing Method

(

)

9

,

7

x = 7

u

x = x =

5

.

5

l

r

Bracketing Method

(

)

9

,

7

x = 7

u

x = x =

5

.

5

l

r

x =

5

.

5

(

+ 7) / 2 = 25

.

6

r

Bracketing Method

x = x =

5

.

5

x = x

l

r

u

r

x =

5

.

5

(

+ 7) / 2 = 25

.

6

r

Bracketing Method:Bisection

Bracketing Method:Bisection

Bracketing Method:Bisection

.

667 38

f ( c) =

1

(

10

c /

1

.

68

e

) − 40 = 0

c

f

)

12

(

= 0669

.

6

38

.

667

f ( c) =

1

(

10

c /

1

.

68

e

) − 40 = 0

c

xu

x

x

l

r

f

)

16

(

= 2

− 2688

.

x = 12

(

+ )

16 / 2 = 14

r

f x

=

f

)

14

(

= 5687

.

1

(

)

1 5687

.

r

(2)

f

)

12

(

= 0669

.

6

x

= x = 14

u

r

38

.

667

f ( c) =

1

(

10

c /

1

.

68

e

) − 40 = 0

c

xu

x

x

l

r

f

)

16

(

= 2

− 2688

.

x = 12

(

+ )

16 / 2 = 14

r

f

)

14

(

= 5687

.

1

x = 14

(

+ )

16 / 2 = 15

38

.

667

r

f ( c) =

1

(

10

c /

1

.

68

e

) − 40 = 0

c

x

x

r

u

xl

f

)

16

(

= 2

− 2688

.

Bracketing Method: Bisection

False-Position Method

False-Position Method

False-Position Method

False-Position Method

False-Position Method

False-Position Method

Open Method:

Simple One-Point Iteration

Open Method:

Simple One-Point Iteration

Open Method:

Simple One-Point Iteration

Open Method:

Simple One-Point Iteration

Open Method:

Simple One-Point Iteration

Open Method:

Newton-Ralphson Method

Open Method:

Newton-Ralphson Method

Open Method:

Newton-Ralphson Method

Open Method:

Newton-Ralphson Method

Open Method:

Newton-Ralphson Method

Open Method:

Secant Method

Open Method:

Secant Method

Open Method:

Secant Method

Multiple Roots

Multiple Roots

Multiple Roots

Multiple Roots

Multiple Roots

Multiple Roots

Multiple Roots

Comparison

Comparison

Comparison

Homework 8

• นักศึกษาต ้องเขียนโปรแกรมช่วยคํานวณ

หรือใช ้ Spreadsheet (MS Excel) ช่วย

คํานวณ

– แนะนําให ้ใช ้ MATLAB

• เขียน Function หรือ Scratch File ก็ได ้

• หรือคํานวณจาก Workspace โดยตรง

• Download คําถามและตอบคําถาม

Document Outline

Table of contents

previous page start